package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/10/07 20:14
 **/
public class Day35_2_Num927_ThreeEqualParts {
    class Solution {
        public int[] threeEqualParts(int[] arr) {
            int cnt = 0;
            int n = arr.length;
            for (int a : arr) {
                cnt += a;
            }
            if (cnt == 0) {
                return new int[]{0, n - 1};
            }
            if (cnt % 3 != 0) {
                return new int[]{-1, -1};
            }
            int eachPart = cnt / 3;
            int idx1 = -1;
            int idx2 = -1;
            int idx3 = -1;
            cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += arr[i];
                if (cnt == 1 && idx1 == -1) {
                    idx1 = i;
                } else if (cnt == eachPart + 1 && idx2 == -1) {
                    idx2 = i;
                } else if (cnt == 2 * eachPart + 1 && idx3 == -1) {
                    idx3 = i;
                }
            }

            while (idx3 < n) {
                if (arr[idx1] == arr[idx2] && arr[idx2] == arr[idx3]) {
                    idx1++;
                    idx2++;
                    idx3++;
                } else {
                    return new int[]{-1, -1};
                }
            }
            return new int[]{idx1 - 1, idx2};
        }
    }
}